package code.oldCode.dynamic;

import java.util.Arrays;

/**
 * @author cuihaoran
 * @date 2024/9/27
 */
public class Dynamic {

    /**
     * 70. 爬楼梯
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        // 数组可以优化掉，本质是斐波那契数列，具体参考下一题
        int[] ans = new int[n];
        // 70和518两个题，分别求排列数和组合数
        // 组合数，先遍历容量
        for (int i = 0; i < n; i++) {
            if (i == 0)
                ans[i] = 1;
            else if (i == 1)
                ans[i] = 2;
            else
                // 再遍历物品，其实就是能走的步数 [1,2]
                ans[i] = ans[i - 1] + ans[i - 2];
        }
        return ans[n - 1];
    }

    /**
     * 509. 斐波那契数
     *
     * @param n
     * @return
     */
    public int fib(int n) {
        // 虽然有通项公式达到O(1)的时间复杂度，不过太复杂
        if (n == 0) return 0;
        else if (n == 1) return 1;
        int a = 0, b = 1;
        int c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    /**
     * 1137. 第 N 个泰波那契数
     *
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        // 虽然有通项公式达到O(1)的时间复杂度，不过太复杂
        if (n == 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 1;
        int a = 0, b = 1, c = 1;
        int d = 0;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    /**
     * 746. 使用最小花费爬楼梯
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        // 到达i所需的最小消费，数组可以优化成两个数，与斐波那契数列一样
        int[] needCost = new int[len + 1];
        needCost[0] = 0;
        needCost[1] = 0;
        for (int i = 2; i <= len; i++) {
            needCost[i] = Math.min(needCost[i - 2] + cost[i - 2], needCost[i - 1] + cost[i - 1]);
        }
        return needCost[len];
    }

    /**
     * 198. 打家劫舍
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0)
            return 0;
        // 选到这里能获利最大多少
        int[] earn = new int[len];
        for (int i = 0; i < len; i++) {
            if (i == 0)
                earn[i] = nums[i];
            else if (i == 1)
                earn[i] = Math.max(nums[i], nums[i - 1]);
            else {
                earn[i] = Math.max(nums[i] + earn[i - 2], earn[i - 1]);
            }
        }
        return earn[len - 1];
    }

    /**
     * 740. 删除并获得点数
     *
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        int[] total = new int[len];  // 数字和
        int[] value = new int[len]; // 数字
        int[] dp = new int[len];
        int v_len = 0;
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] != nums[i - 1])
                v_len++;
            total[v_len] += nums[i];
            value[v_len] = nums[i];
        }
        for (int i = 0; i <= v_len; i++) {
            if (i == 0)
                dp[i] = total[i];
            else if (i == 1) {
                if (value[i] == value[i - 1] + 1)
                    dp[i] = Math.max(dp[i - 1], total[i]);
                else
                    dp[i] = dp[i - 1] + total[i];
            } else {
                if (value[i] == value[i - 1] + 1)
                    dp[i] = Math.max(dp[i - 1], total[i] + dp[i - 2]);
                else
                    dp[i] = dp[i - 1] + total[i];
            }
        }
        return dp[v_len];
    }

    public static void main(String[] args) {
        Dynamic dynamic = new Dynamic();
        System.out.println(dynamic.deleteAndEarn(new int[]{2, 2, 3, 3, 3, 4}));
    }
}
